Internet, mobile communications, navigation, online gaming, sensing technologies and large scale computing infrastructures are producing large amounts of data every day. Big Data is data that is beyond the processing capacity of conventional database systems and analyzing capacity of traditional analyzing methods due to its large volume and fast moving and growing speed. More companies now rely on Big Data to make real-time decisions to solve various problems. Current methods involve utilizing a lot of computational resources, which are very costly, yet still may not satisfy the needs of real-time decision making based on the newest information, especially in the financial industry. How to efficiently, promptly and cost-effectively process and analyze Big Data presents a difficult challenge to data analysts and computer scientists.
Streamed data is data that is constantly being received by a receiver while being delivered by a provider. Streamed data may be real-time data gathered from sensors and continuously transferred to computing devices or electronic devices. Often this includes receiving similarly formatted data elements in succession separated by some time interval. Streamed data may also be data continuously read from storage devices, e.g., storage devices on multi-computing devices which store a Big Data set. Big Data sets are accumulated over time and they may be considered as a data stream with irregular time intervals, so algorithms on streamed data processing may be extended to Big Data processing. Stream processing has become a focused research area recently due to the following reasons. One reason is that the input data are coming too fast to store entirely for batch processing, so some analysis have to be performed when the data streams in. The second reason is that immediate responses to any changes of the data are required in some application domains, e.g., mobile related applications, online gaming, navigation, real-time stock analysis and automated trading, etc. The third reason is that some applications or electronic devices require streaming processing due to their nature, e.g., audio, video and digital TV, etc.
Processing Big Data or streamed data may include performing calculations on multiple data elements. When performing some statistical calculations on Big Data or streamed data, the number of data elements to be accessed could be quite large. For example, when calculating an autocorrelation a (potentially large) number of data elements may need to be accessed.
Further, some statistical calculations are recalculated as outdated data elements are removed from a Big Data set or a data stream. Thus, the (potentially large) number of data elements may need to be repeatedly accessed. For example, it may be that an autocorrelation is calculated for a computation window whose size n keeps decreasing to exclude the accessed or received data element from a Big Data set or a data stream. As such, every time a data element to be removed is accessed or received, the element is removed from the computation window. After a data element is removed from a computation window with a size n, n−1 data elements in the adjusted computation window are then accessed to recalculate the autocorrelation.
When performing an autocorrelation calculation at a given lag using traditional methods on n−1 data elements all the n−1 data elements in the computation window will be visited and used at least once.
Depending on necessity, the computation window size n could be extremely large, so the data elements in a computation window could be distributed over a cloud comprising hundreds of thousands of computing devices. Re-performing an autocorrelation calculation on Big Data sets after some data changing in traditional ways results in slow response and significant waste of computing resources.